/**
 * 剑指 Offer 49. 丑数
 * https://leetcode.cn/problems/chou-shu-lcof/
 */

/**
 * @param {number} n
 * @return {number}
 */
function nthUglyNumber(n) {
  if (n <= 6) {
    return n;
  }
  let next2index = 0;
  let next3index = 0;
  let next5index = 0;
  const list = [1];
  while (list.length < n) {
    const num2 = list[next2index] * 2;
    const num3 = list[next3index] * 3;
    const num5 = list[next5index] * 5;
    const next = Math.min(num2, num3, num5);
    list.push(next);
    if (num2 === next) {
      next2index += 1;
    }
    if (num3 === next) {
      next3index += 1;
    }
    if (num5 === next) {
      next5index += 1;
    }
  }
  return list[n - 1];
}

console.log(nthUglyNumber(1) === 1);
console.log(nthUglyNumber(6) === 6);
console.log(nthUglyNumber(7) === 8);
console.log(nthUglyNumber(10) === 12);
console.log(nthUglyNumber(100) === 1536);
console.log(nthUglyNumber(1690) === 2123366400);
